package leetcode.top100;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [3,0,1]
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: [9,6,4,2,3,5,7,0,1]
 * 输出: 8
 * 说明:
 * 你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
 * <p>
 * <p>
 * 不能够用标记法是因为数组长度是n，但是元素个数如果标记了需要n+1个索引范围。
 *
 * 其他相关问题见{@link leetcode.a_总结分布.Code02_数组中缺失或重复数字}
 * @date 2020/4/15 13:05
 */
public class Code286_FindMissingNum {
    //方式1：排序。时间O(nlogn)
    private static int process1(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) return i;
        }
        return nums.length;
    }

    //方式2：使用hashSet，时空都是O(N)
    private static int process2(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int e : nums) set.add(e);
        for (int i = 0; i < nums.length; i++) {
            if (!set.contains(i)) return i;
        }
        return nums.length;
    }

    //方式3：先把0-n异或，然后再和数组所有元素异或。最后的结果就是缺失的数。相同的数异或得0，有交换律
    private static int process3(int[] nums) {
        int res = nums.length;
        //遍历的时候，把1-n异或了，把数组所有元素异或了，又res初始值为n，所以都异或了
        for (int i = 0; i < nums.length; i++) {
            res = res ^ i ^ nums[i];
        }
        return res;
    }

    //方式4：利用求和。把0-n的值求和，然后再把数组求和，二者相减就是答案。
    private static int process4(int[] nums) {
        int n = nums.length;
        //求和公式n*(n+1)/2,n*(n+1)必定为偶数
        int expectSum = n * (n + 1) / 2;
        for (int i = 0; i < nums.length; i++) {
            expectSum -= nums[i];
        }
        return expectSum;
    }


}
